package stack;

import java.util.List;

/**
 * P206 逆转
 */
public class P206 {
    public static void main(String[] args) {
        P206 p206 = new P206();
        ListNode a=new ListNode(1);
        a.next=new ListNode(2);
        a.next.next=new ListNode(3);
        ListNode listNode = p206.reverseList(a);

        while (listNode!=null){
            System.out.println(listNode.val);
            listNode=listNode.next;
        }
    }

    // 迭代
//    public ListNode reverseList(ListNode head) {
//        if(head==null){
//            return head;
//        }
//
//        ListNode h=new ListNode(head.val);
//        ListNode cur;
//        head=head.next;
//
//        while (head!=null){
//            cur=new ListNode(head.val);
//            cur.next=h;
//            h=cur;
//            head=head.next;
//        }
//
//        return h;
//
//    }
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode listNode = reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return listNode;
    }
}






























/**
 * 递归
 */
class P206Test01 {
//    public ListNode reverseList(ListNode head) {
//        if (head.next == null) {
//            return head;
//        }
//
//        head.next = reverseList(head.next);
//        return head.next;
//    }
}

/**
 * 迭代
 */
class P206Test02 {
//    public ListNode reverseList(ListNode head) {
//        if (head == null)
//            return null;
//        ListNode cur;
//        ListNode node = null;
//
//        while (head != null) {
//            cur = head.next;
//            head.next = node;
//            node = head;
//            head = cur;
//        }
//        head = node;
//
//        return head;
//    }
}

